home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Shareware Overload Trio 2
/
Shareware Overload Trio Volume 2 (Chestnut CD-ROM).ISO
/
dir41
/
timstk11.zip
/
README3.TXT
< prev
next >
Wrap
Text File
|
1993-04-01
|
18KB
|
466 lines
T i m e S t a c k
The Ultimate Software Timing and Stack Analysis Utility
Worst Case Timing And Stack Analysis Increases Quality and
Confidence
During the late 1600's Sir Isaac Newton revolutionized
the scientific community with his laws of gravity and
planetary motion. At the time, these laws appeared
flawless.
However, as new discoveries came to light, it became
apparent that Newton's laws did not work when pushed to
their extremes. By the early 20th century, Albert
Einstein had developed a new set of laws that worked
even at the speed of light.
Many software programs suffer from the same malady.
They work fine under normal conditions, but break down
when pushed to the extreme.
How Many Errors
Many studies have been done to determine the number of
defects in a software program. Figure 1 shows the
results from the University of Maryland's Software
Engineering Laboratory. They measured defects in
software created at NASA's Goddard Space Center. While
it is clear that quality is improving, it will never
reach perfection.
1 TimeStack - The Software Timing and Stack Analysis Tool
Bugs, Errors, Defects
X - Worst
12 -| * - Average
| X O - Best
|
10 -| X
| X
| * X
8 -| *
| * X
| O * X
6 -| O O * * X
| O O * X
| O O *O
4 -|
|
|
2 -|
|
|
0 -+---+-----+-----+-----+-----+-----+-----+-----+-
76 78 80 82 84 86 88 90
Year
Figure 1 Number of bugs, Errors, Defects per 1,000
Lines of Code
Testing software is not easy. It is not unusual to
find that a program thoroughly tested by conventional
methods still contains fatal flaws. AT&T learned the
lesson the hard way on January 15, 1990. A slight
software error disabled nearly half their long distance
lines around the country for almost nine hours.
Error Sensitivity
Obviously software is extremely sensitive to small
errors. Mechanical parts can accommodate a small
variance. Unfortunately, computers only understand
right or wrong; they cannot interpret gray areas. One
tiny error can snowball into a disaster.
Sooner or later, every product is asked to perform at
its limits. However uncommon the situation, when it
happens, will your software meet the challenge?
2 TimeStack - The Software Timing and Stack Analysis Tool
What Can Go Wrong
For someone who writes complex software, it doesn't
take much of an imagination to understand how many
things can go wrong. And, depending upon the product
the software controls, an error can cause a malfunction
resulting in annoyance at the least or a disaster in
critical situations.
Execution time is one area where errors can slip by
until it's too late. A program may get some combination
of inputs that cause it to run longer than its typical
time. Then what? A critical task could get skipped or
run out of order. Tasks could begin to nest and/or
exhaust their stack space. The initial small error has
become a huge problem.
Sometimes a programming or compiler error allows an
imbalanced stack. Something could get put on the stack
but not taken off. Once again, a huge problem can
result from an initial small error.
The Solution
The answer to all of these questions is a TimeStack
analysis.
This analysis will provide, in detail, for every
function, the theoretical:
* maximum execution time,
* minimum execution time,
* worst stack depth usage, and
* possible stack imbalances.
Maximum Execution Time
The theoretical maximum execution time is found by
looking at all possible combination of paths that a
function can take. This is difficult at best to do by
hand for small programs, almost impossible for programs
of any significant size. In programs that must execute
in a given time, this information is essential.
3 TimeStack - The Software Timing and Stack Analysis Tool
Minimum Execution Time
The quickest path through a function is also found.
This is important if some processing must always take
place. A too short execution time could indicate that a
critical function is being skipped.
Worst Stack Depth
It is important to know how much stack a function uses.
A typical amount may not be the same as its worst case.
An overflowed stack usually means overwriting something
important. Almost always the problem crops up at a
distant point from the initial overflow and that makes
it difficult to find.
Stack Imbalances
Most assembly language programmers have accidentally
done this. A typical error would involve putting
something on the stack and forgetting to take it off,
or taking the wrong amount off.
A more subtle stack imbalance occurs when saving values
in the midst of complex logic. With the use of
conditional branches, the possibility arises of putting
something on the stack, while a complex path bypasses
its removal.
Number of Paths
Obviously, the more paths involved in a complex
algorithm, the more possibility for error exists. A
program with only one or two conditional branches is
relatively easy to time and check. But, the possible
number of paths rises exponentially with the addition
of each conditional branch.
The worst case or maximum number of paths in a program
increases by 2^n where 'n' is the number of conditional
branches. The minimum number of paths is n + 1.
In the typical program, neither of these extremes are
realistic. However, they do provide a set of
boundaries. Figure 2 shows these limits graphed as a
function of the number of conditional branches.
4 TimeStack - The Software Timing and Stack Analysis Tool
Possible paths
X - Worst
100000 -| X O - Best
|
|
10000 -| O
|
|
1000 -| X O
|
|
100 -| O
| X
|
10 -| O
|
| XO
1 -+---XO------+-------+-------+-------+-------+-
0 1 10 100 1000 10000
Number of conditional branches
Figure 2 Number of Paths vs. Number of Conditional
Branches
Most programs average a conditional branch every 10 to
20 bytes. A small 100 byte function would thus have an
average of least five conditional branches. That means
just this simple procedure all by itself would have
between six and 32 possible paths. Now imagine how many
paths a 100K program must have!
How To Check
How do the engineers in your company time and check
their programs? Have they ever been checked completely?
Clearly, a program of any complexity quickly becomes
almost impossible to check. Many times it becomes
necessary to just cross your fingers and hope it works.
The methods most commonly used simply cannot handle
complex programs.
Impractical To Do It Manually
With the number of possible paths in a program of any
complexity, it is apparent that hand counting the
execution time is a near-impossible task. Even if one
were to sit and methodically examine each possible
path, the probability of missing one is tremendous. And
5 TimeStack - The Software Timing and Stack Analysis Tool
of course, the time wasted on this endeavor could be
much more efficiently used for other aspects of
programming.
Logic Analyzers
It would seem that a logic analyzer could do the job.
It would -- but only if the software executes in a
simple linear fashion. As long as there are no
decisions to be made that can change the direction of
flow, it will work fine.
It becomes more complex if the timing depends upon the
state of an input switch. Then you have to look at the
switch in both positions. What if the timing depends on
an interaction with a number of inputs? Or a calculated
value? Using a logic analyzer quickly becomes
cumbersome and is still unlikely to catch the absolute
maximum path.
Simulators
A simulator relies upon user input to configure the
simulator to try a finite number of branches. It will
time the maximum execution time -- if you tell it which
path that is. A simulator does not try every possible
combination of execution paths looking for maximum and
minimum execution times, deepest stack depth or stack
imbalances.
Even if the simulator follows a test suite, tests
inputs at their limits or does random combinations in
between, that still does not guarantee it will find the
answers to those nagging questions.
Profilers
A profiler is no better than a logic analyzer. Once
again, it depends upon the user to determine the inputs
and execution paths. You can never be sure the maximum
path or stack has been found.
The Cost Of Failure
When a software program fails to carry out its
appointed task, it is difficult to calculate the cost
of failure. Deciding how to assess these costs is a
6 TimeStack - The Software Timing and Stack Analysis Tool
decision each company must come to on its own. It has
been mentioned because it is important when balancing
the cost of testing with the cost of failure.
Slightly Pessimistic
A timing and stack analysis has one weakness: the
results may be slightly pessimistic with some
algorithms. This is typically caused by functions that
are mutually exclusive but are timed together anyway.
Nevertheless, it would be nice to have that safe
feeling that your program will perform even under
unrealistic circumstances. And isn't it better to err
on the conservative side?
Standards for Government Software Development
Government document DOD-STD-2167A relates to the
acquisition, development, or support of software
systems. In paragraph 4.2.1 it says "The contractor
shall use systematic and well documented software
development methods to perform ... testing of the
deliverable software." Paragraph 5.4.2.5: "The
contractor's ... testing shall include stressing the
software at the limits of its specified requirements."
It would seem prudent to include a TimeStack analysis
to know where those limits are.
Aviation Industry Guidelines
Manufactures of aviation products have devised a series
of guidelines for their equipment. Document RTCA/DO-
178A, titled "Software Considerations in Airborne
Systems and Equipment Certification", proposes
guidelines for software in avionics and flight critical
functions.
For obvious reasons, design, verification, and testing
are very important in this area. It mentions the
importance of execution flow and timing, measuring CPU
utilization, and software input transient load effects.
A TimeStack analysis is of great benefit to these types
of programs.
7 TimeStack - The Software Timing and Stack Analysis Tool
Bibliography
F. W. Blakely and M. E. Boles, "A Case Study of Code
Inspections," Hewlett-Packard Journal, Vol 42 no. 4,
October 1991, pp. 58-63.
F. P. Brooks, Jr., "The Mythical Man-month," Addison-
Wesley, 1975.
T. H. Cormen, C. E. Leiserson and R. L. Rivest,
"Introduction to Algorithms," McGraw-Hill, 1990.
R. B. Grady and D. L. Caswell, "Software Metrics:
Establishing a Company-wide Program," Prentice-Hall,
1987.
L. Lee, "The Day The Phones Stopped," Donald I. Fine,
Inc., 1991.
D. L. Parnas, A. J. van Schouwen, and S. P. Kwan,
"Evaluation of Safety-Critical Software," Commun. ACM,
Vol 33 no. 6, June 1990, pp. 636-648.
R. Resnick and D. Halliday, "Physics, Part I," John
Wiley & Sons, Third edition, 1977.
E. I. Schwartz, "Turning Software From a Black Art into
a Science," Business Week, October 25, 1991, pp. 80.
W. T. Ward, "Calculating the Real Cost of Software
Defects," Hewlett-Packard Journal, Vol. 42 no. 4,
October 1991, pp. 55-58.
8
